package LeetCode;

import java.util.Arrays;
import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}20:51
 */
public class LeetCode120 {
    // 自上而下的进行
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0){
            return 0;
        }
        int n = triangle.size();
        int m = triangle.get(n - 1).size();// 最后一行的长度
        // 构建二维数组
        int[][] dp = new int[n][m];
        // 初始化dp[0][0]
        dp[0][0] = triangle.get(0).get(0);
        // 第一列只能向下计算
        for (int i = 1; i < n; i++){
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        }

        for (int i = 1; i < n; i++){
            int j = 1;
            // 这里计算的是三角形每一行的长度都不一样
            // 最后一列单独计算，因为是斜边，所以从遍历的个数是size - 1
            while(j<triangle.get(i).size()-1) {
                //状态转移公式
                dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + triangle.get(i).get(j);
                ++j;
            }
            //三角形斜边需要单独计算
            dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
        }
        return Arrays.stream(dp[n-1]).min().getAsInt();
    }

    // 自下而上的走法 可以简化斜边和第一列的细节问题
    public int minimumTotal2(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0){
            return 0;
        }
        int n = triangle.size() + 1;
        int m = triangle.get(n - 1).size() + 1;// 最后一行的长度 之所以以要多加一行，是因为状态转移公式变化导致的，为了处理一些边界条件所以增加了一行
        int[][] dp = new int[n][m];
        // 先填值
        for (int i = n - 2; i > 0; i--){
            for (int j=triangle.get(i).size()-1;j>=0;--j){

                dp[i][j] = Math.min(dp[i + 1][j + 1],dp[i + 1][j]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}
